
struct _tree{
  char c;
  struct _tree *next, *down;
};

typedef struct _tree tree;

tree nil = {'\0', NULL, NULL};
tree *pool = NULL;


tree *lookup(char *s){
  tree **o = &pool, *n = NULL, *m;
  while(*s){
    while((n = *o) && *s > n->c){
      o = &n->next;
    }
    if(n && *s == n->c){
      o = &n->down;
      s++;
    }else{
      m = malloc(sizeof(tree));
      m->c = *s;
      m->next = n;
      *o = n = m;
      while(*++s){
	o = &n->down;
	n = malloc(sizeof(tree));
	n->c = *s;
	n->next = NULL;
	*o = n;
      }
      n->down = NULL;
      break;
    }
  }
  return n;
}

tree *lookupid(identifier id){
  return lookup(PyString_AsString(id));
}


struct _environment{
  tree *id;
  struct _environment *prev;
};
typedef struct _environment environment;

typedef struct{
  int size;
  tree *data[0];
} arraylist;

arraylist *arraylist_create(int capacity) {
  arraylist *l;
  l = (arraylist *)malloc(sizeof(arraylist)+sizeof(tree *)*capacity);
  l->size = 0;
  return l;
}

//return index of item (find using binary search)
int arraylist_search(arraylist *l, tree *needle) {
  int mid;
  int low = 0;
  int high = l->size;

  while (low < high) {
    mid = (low + high) / 2; //check between upper and lower limits
    if (l->data[mid] > needle) {//if needle is smaller than mid
      high = mid; //set upper limit just below mid
    } else if (l->data[mid] < needle) { //if needle is larger than mid
      low = mid+1; //set lower limit just above mid
    } else { //if needle is not smaller than mid and not larger than mid
      return mid;//found !
    }
  }
  return -1; // not found 
}


//insert item in the end
void arraylist_insert(arraylist *l, tree *obj) {
  (l->data)[l->size] = obj;
  (l->size)++;
}

int local_search(environment *env, tree *needle){
  int i;
  for(i = 0 ; env->id != needle ; i++)
    env = env->prev;
  return i;
}

void add_local(environment **env, identifier id) {
  char *name = PyString_AsString(id);
  
  //get the tree pointer corresponding to the string name
  tree *tid = lookup(name);

  environment *new = (environment *)malloc(sizeof(environment));
  new->id = tid;
  new->prev = *env;
  *env = new;
}

void add_env(environment **env, identifier id) {
  char *name = PyString_AsString(id);
  
  //get the tree pointer corresponding to the string name
  tree *tid = lookup(name);

  while(*env && tid > (*env)->id)
    env = &(*env)->prev;
  if(!*env || tid != (*env)->id){
    //make new environment element
    environment *new = (environment *)malloc(sizeof(environment));
    new->id = tid;
    new->prev = *env;
    *env = new;
  }
}

//builds an arraylist with trees as data from an environment linked list.
arraylist *convert_env(environment *env) {
  environment *current;
  int size = 0;
  for(current = env ; current ; current = current->prev){
    size++;
  }
  arraylist *l = arraylist_create(size);
  while (env) {
    arraylist_insert(l,env->id);
    env = env->prev;
  }
  return l;
}
